﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions
{
    /*
     * The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the 9-digit number, 134217728=8^9, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

     * */
    class Problem63 : IProblem
    {
        public string Calculate()
        {
            //taktika: isprobavat sve potencijale, i brojat im znamenke - digitronom


            //na prvu
            //1..9 = 9 brojeva
            //na drugu
            //4, 5, 6, 7, 8, 9 = 6 brojeva
            //na trecu
            //5, 6, 7, 8, 9 = 5 brojeva
            //na cetvrtu
            //6, 7, 8, 9 = 4 broja
            //na petu
            //7, 8, 9 = 3 broja
            //na sestu
            //7, 8, 9 = 3 broja
            //na sedmu
            //8, 9 = 2 broja
            //na osmu
            //8, 9 = 2 broja
            //na devetu
            //8, 9 = 2 broja
            //na desetu
            //8, 9 = 2
            //na jedanestu
            //9 = 1
            //na dvanestu
            //9 = 1
            //na trinestu 1
            //do 9^21: 14, 15, 16, 17, 18, 19, 20 i 21 = 8
            //49 sve skupa

            int n = 0;
            int count = 0;
            while (true)
            {
                n++;
                bool hasOne = false;
                for (uint a = 1; a < 10; a++)
                {
                    BigInteger result = 1;
                    for (int i = 0; i < n; i++)
                        result *= a;

                    if (CommonFunctions.NumberOfDigits(result) == n)
                    {
                        hasOne = true;
                        count++;
                    }
                }

                if (!hasOne)
                    break;
            }


            return count.ToString();
        }
    }
}
